package top.dprkshow.practice.graph;

/**
 * @author Kent HAN
 * @date 2021/9/13
 */
public class Bipartite {
    private boolean isBipartite;
    private boolean[] visited, color;

    public Bipartite(MatrixGraph g) {
        isBipartite = true;
        visited = new boolean[g.getTotalVertices()];
        color = new boolean[g.getTotalVertices()];
    }

    public void init(MatrixGraph g) {
        for (int i = 0; i < g.getTotalVertices(); i++) {
            if (!visited[i]) {
                dfs(g, i);
            }
        }
    }

    private void dfs(MatrixGraph g, int source) {
        visited[source] = true;
        for (Integer adjVertex : g.adj(source)) {
            if (!visited[adjVertex]) {
                color[adjVertex] = !color[source];
                dfs(g, adjVertex);
            } else if (color[adjVertex] == color[source]) {
                isBipartite = false;
            }
        }
    }
}
